//
// Created by gushen610140 on 2024/4/18.
//

#ifndef DATASTRUCTURECOURSE_GFORESTTREE_H
#define DATASTRUCTURECOURSE_GFORESTTREE_H

#include <iostream>
#include "GStaticQueue.h"

template<typename T>
class GForestNode {
public:
    T value;
    GForestNode<T> *firstChild;
    GForestNode<T> *nextSibling;

    explicit GForestNode(T value) : value(value), firstChild(nullptr), nextSibling(nullptr) {}
};

template<typename T>
class GForestTree {
private:
    GForestNode<T> *_root;

protected:
    [[maybe_unused]] GForestNode<T> *getRoot() {
        return _root;
    }

    void _create(GStaticQueue<GForestNode<T> *> &queue) {
        // 以二元组的方式接收，具有顺序
        T parent, child;
        std::cin >> parent >> child;
        auto curNode = new GForestNode<T>(child);
        // 不断出队直到找到父节点
        while (queue.get_front()->value != parent) {
            queue.pop_front();
        }
        auto parentNode = queue.get_front();
        // 是第一个孩子就在左子树
        if (!parentNode->firstChild) {
            parentNode->firstChild = curNode;
        } else {
            // 不是第一个孩子就在左子树的最右边
            auto currentChild = parentNode->firstChild;
            while (currentChild->nextSibling) {
                currentChild = currentChild->nextSibling;
            }
            currentChild->nextSibling = curNode;
        }
        // 新建的节点符合顺序
        queue.push_back(curNode);
    }

    virtual void printPreorder(GForestNode<T> *node) {
        if (!node) {
            return;
        }
        std::cout << node->value << " ";
        printPreorder(node->firstChild);
        printPreorder(node->nextSibling);
    }

    virtual void _printPostorder(GForestNode<T> *node) {
        if (!node) {
            return;
        }
        _printPostorder(node->firstChild);
        std::cout << node->value << " ";
        _printPostorder(node->nextSibling);
    }

    int getDepth(GForestNode<T> *node) {
        if (!node) {
            return 0;
        }
        return std::max(getDepth(node->firstChild) + 1, getDepth(node->nextSibling));
    }

    int getLeavesCount(GForestNode<T> *node) {
        if (!node) {
            return 0;
        }
        if (!node->firstChild) {
            return 1 + getLeavesCount(node->nextSibling);
        }
        return getLeavesCount(node->firstChild) + getLeavesCount(node->nextSibling);
    }

public:
    GForestTree() : _root(nullptr) {}

    [[maybe_unused]] void create() {
        int tupleNum;
        std::cin >> tupleNum;
        GStaticQueue<GForestNode<T> *> queue;
        _root = new GForestNode<T>(-1);
        queue.push_back(_root);
        for (int i = 0; i < tupleNum; i++) {
            _create(queue);
        }
    }

    [[maybe_unused]] virtual void printPreorder() {
        std::cout << "PreOrder: ";
        printPreorder(_root->firstChild);
        std::cout << std::endl;
    }

    [[maybe_unused]] virtual void printPostorder() {
        std::cout << "PostOrder: ";
        _printPostorder(_root->firstChild);
        std::cout << std::endl;
    }

    [[maybe_unused]] virtual void printDepth() {
        std::cout << "Depth: " << getDepth(_root->firstChild) << std::endl;
    }

    [[maybe_unused]] void printLeavesCount() {
        std::cout << "Number of leaves: " << getLeavesCount(_root->firstChild) << std::endl;
    }
};

// 主要是为了重写一下 print 方法和 create 方法
template<typename T>
class [[maybe_unused]] GForestTreeInherit : public GForestTree<T> {
private:
    // {}实现默认初始化，c++11特性
    GForestNode<T> *root{};

protected:
    void _printLeaves(GForestNode<T> *node) {
        if (!node) {
            return;
        }
        if (!node->firstChild) {
            std::cout << node->value << " ";
            _printLeaves(node->nextSibling);
            return;
        }
        _printLeaves(node->firstChild);
        _printLeaves(node->nextSibling);
    }

    GForestNode<T> *_createPreorder() {
        T value;
        std::cin >> value;
        if (!value || value == '#') {
            return nullptr;
        }
        auto node = new GForestNode<T>(value);
        node->firstChild = _createPreorder();
        node->nextSibling = _createPreorder();
        return node;
    }

public:
    // 在父类的树创建完成后再继承根节点
    [[maybe_unused]] void inheritRoot() {
        // 继承根节点顺便舍去虚拟头节点
        root = GForestTree<T>::getRoot()->firstChild;
    }

    void printDepth() override {
        std::cout << GForestTree<T>::getDepth(root);
    }

    [[maybe_unused]] void printLeaves() {
        _printLeaves(root);
        std::cout << std::endl;
    }

    [[maybe_unused]] void createPreorder() {
        root = _createPreorder();
    }

    void printPreorder() override {
        std::cout << "PreOrder: ";
        printPreorder(root);
        std::cout << std::endl;
    }

    void printPreorder(GForestNode<T> *node) override {
        if (!node) {
            return;
        }
        std::cout << node->value;
        printPreorder(node->firstChild);
        printPreorder(node->nextSibling);
    }

    void printPostorder() override {
        std::cout << "InOrder: ";
        _printPostorder(root);
        std::cout << std::endl;
    }

    void _printPostorder(GForestNode<T> *node) override {
        if (!node) {
            return;
        }
        _printPostorder(node->firstChild);
        std::cout << node->value;
        _printPostorder(node->nextSibling);
    }
};

#endif //DATASTRUCTURECOURSE_GFORESTTREE_H
